% Agregamos esto para poder hacer las pruebas.
?- dynamic llega/3.

%% Rutas aéreas predefinidas.

% llega(?origen, ?destino, ?tiempo)
llega(buenos_aires, mdq, 1).
llega(buenos_aires, cordoba, 2).
llega(buenos_aires, rio, 4).
llega(buenos_aires, madrid, 12).
llega(buenos_aires, atlanta, 11).
llega(mdq, buenos_aires, 1).
llega(cordoba, salta, 1).
llega(salta, buenos_aires, 2).
llega(rio, buenos_aires, 4).
llega(rio, new_york, 10).
llega(atlanta, new_york, 3).
llega(new_york, madrid, 9).
llega(madrid, lisboa, 1).
llega(madrid, buenos_aires, 12).
llega(lisboa, madrid, 1).
llega(new_york, buenos_aires, 11).

%% Aviones y sus autonomías.

% autonomia(?avion, ?horas)
autonomia(boeing_767, 15).
autonomia(airbus_a320, 9).
autonomia(boeing_747, 10).


% Esto no estaba en la base de conocimiento, lo agreguamos porque no tenemos 
% reglas para checkear si algo es una aerolinea válida.
%
% Estado de aerolinea del enunciado: 
aerolinea([ [rio,[airbus_a320]], [buenos_aires, [airbus_a320, boeing_767]], [cordoba, [airbus_a320]], [atlanta, [boeing_747]] ]).

%% Predicados pedidos:

% _____________________________________________________________________________
% Ejercicio 1
% ciudades(-Ciudades).
%
% -----------------------------------------------------------------------------
% Como las predicado llega(Ciudad, Ciudad, Tiempo) definen las ciudades, 
% juntamos todas las primeras y segundas compenentes de estos predicados, 
% usando setof para quedarnos con todas las ciudades, pero sin que estén 
% repetidas. 

ciudades(Ciudades) :- setof(X, esCiudad(X), Ciudades). 

esCiudad(X) :- llega(X, _, _).
esCiudad(X) :- llega(_, X, _).

% _____________________________________________________________________________
% Ejercicio 2
% viajeDesde(+Origen, ?Destino, -Recorrido, -Tiempo). -- Devuelve infinitos resultados.
%
% -----------------------------------------------------------------------------
% Caso Base: El origen es igual al destino, entonces la lista de ciudades 
%            visitadas tiene un solo elemento que es el origen, y el 
%            tiempo del viaje es 0.
%
% Caso Recursivo: Si se saben los viajes desde una ciudad hasta el destino 
%                 buscado, y si además desde la ciudad origen se puede 
%                 llegar hasta esa ciudad, entonces, se usa esa información 
%                 para calcular un nuevo viaje que pase por esa ciudad.
%                 Recorrido = Origen, recorrido de Ciudad hasta Destino.
%                 Tiempo = Tiempo que se tarda en ir desde Origen a Ciudad + 
%                          Tiempo que se tarda en ir desde Ciudad a Destino.

viajeDesde(Orig, Orig, [Orig], 0).
viajeDesde(Orig, Dest, [Orig | Rec], Tiempo) :-
            viajeDesde(Ciudad, Dest, Rec, Tiempo2), 
            llega(Orig, Ciudad, Tiempo1), 
            Tiempo is Tiempo1 + Tiempo2.  


% _____________________________________________________________________________
% Ejercicio 3
% viajeSinCiclos(+Origen, ?Destino, -Recorrido, -Tiempo).
%
% -----------------------------------------------------------------------------
% Para obtener un viaje sin ciclos que que hacemos es usar un predicado 
% adicional, recorrerSinCiclos que recibe otro parámeotro que es la lista 
% de ciudades visitadas hasta el momento. Lo que se quiere es evitar visitar 
% esas ciudades que ya fueron visitadas.
% Para cada ciudad vecina de Origen, si se puede llegar hasta destino y además 
% esa ciudad no pertenece a las ya visitadas, entonces se pasa por ella para 
% tener un nuevo camino. 
% Al igual que en el ejercicio anterior, se suman los tiempos y los recorridos 
% se modifican adecuadamente. 
% La búsqueda en el grafo se realiza utilizando bfs.

viajeSinCiclos(Orig, Dest, Rec, Tiempo) :- 
            setof(_, recorrerSinCiclos(Orig, Dest, Rec, Tiempo,[Orig]), _).

recorrerSinCiclos(Orig, Orig, [Orig], 0, _).
recorrerSinCiclos(Orig, Dest, [Orig | Rec], Tiempo, Visitados) :- 
			llega(Orig, Ciudad, T1), 
			not(member(Ciudad, Visitados)), 
			recorrerSinCiclos(Ciudad, Dest, Rec, T2, [Ciudad | Visitados]),
			Tiempo is T1 + T2.


% _____________________________________________________________________________
% Ejercicio 4
% viajeMasCorto(+Origen, +Destino, -Recorrido, -Tiempo).
%
% -----------------------------------------------------------------------------
% En este caso lo que hacemos es juntar todos los recorridos posibles sin 
% ciclos dados por el predicado viajeSinCiclos y quedarnos con los de 
% recorrido mínimo. Una vez obtenidos estos recorridos, aplicamos setof 
% para quedarnos con uno solo.

viajeMasCorto(Orig, Dest, Rec, T) :- 
            setof(_, juntarRecorridos(Orig, Dest, Rec, T), _).

juntarRecorridos(Orig, Dest, Rec, T) :- 
            setof([Rec1, T1], viajeSinCiclos(Orig, Dest, Rec1, T1), Xs), 
            minRecorrido(Xs, Rec, T).

minRecorrido([[Rec, T]], Rec, T).
minRecorrido([[Rec1, T1], [_, T2] | Xs], Rec, T) :- 
            T1 < T2,  minRecorrido([[Rec1, T1] | Xs], Rec, T).
minRecorrido([[Rec1, T1], [_, T2] | Xs], Rec, T) :- 
            T1 == T2, minRecorrido([[Rec1, T1] | Xs], Rec, T).
minRecorrido([[_, T1] , [Rec2 , T2] | Xs], Rec, T) :- 
            T1 == T2, minRecorrido([[Rec2, T2] | Xs], Rec, T).
minRecorrido([[_, T1] , [Rec2, T2] | Xs], Rec, T) :- 
            T1 > T2,  minRecorrido([[Rec2, T2] | Xs], Rec ,T).


% _____________________________________________________________________________
% Ejercicio 5
% grafoCorrecto
% 
% -----------------------------------------------------------------------------
% Para ver que el grafo es correcto, obtenemos todas las ciudades y luego 
% vemos que esa lista represente nodos de un grafo conexo.
%
% Para ver si es conexo, el predicado conexo recibe dos listas con nodos, donde 
% la segunda lista representa a todos los nodos del grafo y la primera a un 
% subconjunto de estos mismos nodos.  
% Caso Base: No hay nodos, entonces es conexo.
% Caso Recursivo: Si hay por lo menos un nodo, ver que esté conectado a todos, 
%                 y que el resto de los nodos también cumplan esta propiedad.
%
% Para ver si un nodo está conectado con todos los nodos lo que se hace es ver 
% que exista algún camino (viaje sin ciclos) desde el hasta todos los nodos.

grafoCorrecto :- ciudades(Xs), conexo(Xs, Xs).

conexo([], _).
conexo([X | Xs], Ys) :- conectadoCon(X, Ys), conexo(Xs, Ys).

conectadoCon(_, []).
conectadoCon(X, [X1 | Xs]) :- 
            viajeSinCiclos(X, X1 ,_ ,_), 
            conectadoCon(X, Xs).


% _____________________________________________________________________________
% Ejercicio 6
% cubreDistancia(+Recorrido, ?Avion).
%
% -----------------------------------------------------------------------------
% Caso Base 1 : Recorrido Vacío entonces se cubre la distancia.
% Caso Base 2 : Recorrido de una sola ciudad entonces se cubre la distancia, 
%               porque el avion no se mueve de esa ciudad, nunca hace ningún 
%               viaje.
% Caso Recursivo: Hay por lo menos dos ciudades en el recorrido, que son las 
%                 dos primeras, Origen y Destino. Como se permite cargar 
%                 combustible en las escalas, solamente hace falta controlar 
%                 que entre dos ciudades vecinas alcance el combustible. 
%                 Para esto, se checkea que la autonomía del avion sea mayor 
%                 o igual al tiempo que se tarda en viajar entre esas ciudades.
%                 En este caso, el viaje es entre Origen y Destino porque son 
%                 las dos primeras ciudades del recorrido. Luego, se cubre la 
%                 distancia, si también vale para el resto del recorrido, es 
%                 decir sacando a la ciudad Origen. 

cubreDistancia([], _).
cubreDistancia([_], _).
cubreDistancia([Orig, Dest | Rec], Avion) :- 
            llega(Orig, Dest, T), 
            autonomia(Avion, T1), 
            T =< T1, 
            cubreDistancia([Dest | Rec], Avion).


% _____________________________________________________________________________
% Ejercicio 7
% vueloSinTransbordo(+Aerolinea, +Ciudad1, +Ciudad2, ?Tiempo, ?Avion).
%
% -----------------------------------------------------------------------------
% Esta función utiliza varios de los predicados ya definidos, para saber si 
% Ciudad1 y Ciudad2 son ciudades, para obtener el tiempo T del viaje más corto 
% entre Ciudad1 y Ciudad2 y cubreDistancia para saber si el avión puede 
% realizar ese recorrido (que es el que corresponde al viaje más corto).
% Como nuevos predicados se tienen los relacionados a una aerolínea.
vueloSinTransbordo(Aerolinea, Ciudad1, Ciudad2, Tiempo, Avion) :- 
            esAerolinea(Aerolinea), 
            ciudades(Ciudades),
			member(Ciudad1, Ciudades),
			member(Ciudad2, Ciudades),
			aerolineaTieneAvionEn(Aerolinea, Ciudad1, Avion), 
			viajeMasCorto(Ciudad1, Ciudad2, Recorrido, Tiempo),
			cubreDistancia(Recorrido, Avion).

% Una lista es una aerolinea, cuando está compuesta por elementos de la forma 
% [Ciudad, L] donde L es una lista de aviones. 
% Por lo tanto, checkeamos que para cada elemento, la primera componente sea 
% efectivamente una ciudad y la segunda sea una lista de aviones.
esAerolinea([]).
esAerolinea([[Ciudad, Aviones] | Aerolineas]) :-  
            ciudades(Ciudades), 
            member(Ciudad, Ciudades), 
            avionesValidos(Aviones), 
            esAerolinea(Aerolineas).

% Lista de aviones, están definidos por los predicados autonomia.
aviones(Aviones) :- setof(Avion, T ^ autonomia(Avion, T), Aviones).

% Los aviones válidos son los que pertenecen a la lista de aviones.
% Con esta función lo que hacemos es ver que todos los elementos de una lista 
% sean efectivamente aviones.
avionesValidos([]).
avionesValidos([Avion | Aviones]) :- 
            aviones(Xs), 
            member(Avion, Xs), 
            avionesValidos(Aviones).

% Este predicado indica si la aerolínea posee un avion en la ciudad Ciudad.
% Como cada elemento de la aerolínea es de la forma [Ciudad1, Aviones] puede 
% pasar que:
% Caso Base: Efectivamente la ciudad buscada sea esa ciudad y el avión 
%            pertenezca a la lista de aviones, en cuyo caso ya se sabe que 
%            existe el avión.
% Caso Recursivo 1: La ciudad no sea igual a la buscado, en cuyo caso el 
%                   predicado será cierto si en el resto de la aerolínea se 
%                   cumple que existe el avión en esa ciudad.
% Caso Recursivo 2: La ciudad es igual a la buscada, pero el avión no 
%                   pertenece a la lista de aviones. Entonces en este caso 
%                   también el predicado será cierto si en el resto de la 
%                   aerolínea existe el avión en esa ciudad.
aerolineaTieneAvionEn([[Ciudad1, Aviones] | _] , Ciudad, Avion) :- 
            Ciudad1 == Ciudad,  
            member(Avion, Aviones).
aerolineaTieneAvionEn([[Ciudad1, _] | Xs] , Ciudad, Aviones) :- 
            Ciudad1 \== Ciudad,  
            aerolineaTieneAvionEn(Xs, Ciudad, Aviones).
aerolineaTieneAvionEn([[Ciudad1, Aviones] | Xs] , Ciudad , Avion) :- 
            Ciudad1 == Ciudad, 
            \+ member(Avion, Aviones), 
            aerolineaTieneAvionEn(Xs, Ciudad, Aviones).



% _____________________________________________________________________________
?- [pruebas].
